package com.cwj.lab4.SORT;

import com.cwj.lab4.Tool;

/**
 * 堆排序
 * 由大到小排序
 * */
public class HeapSort<T extends Comparable<T>>implements Sorted<T> {
    //根节点下降
    /**
     * @param ind 下降得索引
     * @param end 堆长度
     * @param nums 要排序的数组
     * */
    public void down(T[]nums,int end,int ind){
        int lef=0,rig=0;
        while((lef=ind*2+1)<=end){
            //lef=ind*2+1;
            rig=lef+1;
            if(rig<=end&&nums[lef].compareTo(nums[rig])<0){
                lef=rig;
            }
            int sig=nums[ind].compareTo(nums[lef]);
            if(sig<0){
                Tool.swap(nums,ind,lef);
                ind=lef;
            }else{
                break;
            }
        }
    }
//    建堆
    private void createHeap(T[]nums){
        int len=nums.length/2-1;//其除以2是为了找到最后一个非终端节点，而-1是为了编号和下标的对齐
        T temp=null;
        for (int i = len; i >=0 ; i-=1) {
            temp=nums[i];
            this.down(nums,nums.length-1,i);
        }
    }
    //排序
    public void Sort(T[]nums){
        createHeap(nums);
//        this.show(nums);
        int len=nums.length;
        for(int i=0;i<len-1;i+=1){
            Tool.swap(nums,0,len-i-1);
            this.down(nums,len-i-2,0);
        }
    }
    //展示堆结构
    public void show(T[]nums){
        int j=0,start=0;
        for (int i = 1; i <nums.length ; i*=2) {
            for (j = 0; j < i&&j+start<nums.length; j++) {
                System.out.print(nums[j+start]+" ");
            }
            System.out.println();
            start=j;
        }
    }
}
